package chapter04_RecursionAndDynamic.feibona;


/**
 * 描述：
 *  跳台阶，一次可以跨越2个或者一个台阶，返回有多少种走法
 * @author hl
 * @date 2021/6/3 11:49
 */
public class SkipStep {
    public static void main(String[] args) {
        SkipStep ss = new SkipStep();
        int n = 10;
        System.out.println(ss.s1(n));
        System.out.println(ss.s2(n));
        System.out.println(ss.s3(n));
    }
    public int s1(int n){
        if(n < 1){
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return s1(n - 1) + s1(n - 2);
    }

    public int s2(int n){
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int f = 1, s = 2, temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = f + s;
            f = s;
            s = temp;
        }
        return s;
    }

    /**
     * 这也是一个二阶递推数列，可以根据2*2的矩阵乘法的形式表示，根据数列的前4项可以退出矩阵为[[1,1],[1,0]]
     * @param n
     * @return
     */
    public int s3(int n){
        if (n < 0) {
            return 0;
        }
        if (n < 3) {
            return n;
        }
        int[][] base = {{1, 1}, {1, 0}};
        int[][] res = MatrixPower.matrixPower(base, n - 2);
        return  2 * res[0][0] + res[1][0];
    }
}
